package Demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-09-04
 * Time: 14:29
 */
public class Test {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //恢复二叉搜索树
    public TreeNode[] tree = new TreeNode[4];
    public TreeNode prev;
    public int i = 0;
    public void findError(TreeNode root){
        if(root == null) return;
        //中序遍历

        //遍历左子树
        findError(root.left);

        //处理中间节点
        if(prev == null){
            prev = root;
        }else{
            //判断前后关系
            if(root.val < prev.val){
                tree[i++] = prev;
                tree[i++] = root;
            }
            prev = root;
        }

        //遍历右子树
        findError(root.right);
    }

    public void recoverTree(TreeNode root) {
        findError(root);
        //冒泡排序
        boolean flag = false;
        for(int j = 0;j < i - 1;j++){
            for(int k = 0;k < i - 1 - j;k++){
                if(tree[k].val > tree[k + 1].val){
                    int temp = tree[k].val;
                    tree[k].val = tree[k + 1].val;
                    tree[k + 1].val = temp;
                    flag = true;
                }
            }
            if(!flag) break;
        }
    }

    public static void main(String[] args) {

    }
}
